package bintree.heap.leetcode;

import java.util.*;

/**
 * @Author: yuisama
 * @Date: 2021/9/13 15:41
 * @Description:前K个高频单词
 * 给一非空的单词列表，返回前 k 个出现次数最多的单词。
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
 * 示例 1：
 * 输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
 * 输出: ["i", "love"]
 * 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
 *     注意，按字母顺序 "i" 在 "love" 之前。
 * 链接：https://leetcode-cn.com/problems/top-k-frequent-words
 */
public class Num692 {
    // Map+排序方式 O(NlogN)时间复杂度
    public List<String> topKFrequent(String[] words, int k) {
        // 存储所有单词以及出现频次的哈希表
        List<String> ret = new ArrayList<>();
        Map<String,Integer> wordsTable = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (wordsTable.containsKey(words[i])) {
                // 取出当前单词出现频次并++
                int times = wordsTable.get(words[i]);
                wordsTable.put(words[i],times + 1);
            }else {
                // 同步也将不重复单词存入结果集中
                wordsTable.put(words[i], 1);
                ret.add(words[i]);
            }
        }
        // 将List中所有结果排序，按照出现次数降序排序
        ret.sort((s1, s2) ->
                wordsTable.get(s1) == wordsTable.get(s2) ? s1.compareTo(s2) :
                        wordsTable.get(s2) - wordsTable.get(s1));
        // 此时List中存储按照出现频次从大到小的顺序排列的所有单词，截取前k个即可
        return ret.subList(0,k);
    }

    // Map + 优先级队列 O(NlogK)
    public List<String> topKFrequent1(String[] words, int k) {
        List<String> retList = new ArrayList<>(k);
        Map<String,Integer> wordsTable = new HashMap<>();
        // 因为要找到出现频率最高的K个单词，因为维护一个k个单词小根堆
        PriorityQueue<String> queue = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // 当O1与O2出现频率相同时，比较两个单词大小，否则出现频率越高的优先级也越大
                return wordsTable.get(o1) == wordsTable.get(o2) ? o2.compareTo(o1) :
                        wordsTable.get(o1) - wordsTable.get(o2);
            }
        });
        // 向哈希表中添加元素
        for (int i = 0; i < words.length; i++) {

            if (wordsTable.containsKey(words[i])) {
                int val = wordsTable.get(words[i]);
                wordsTable.put(words[i], val + 1);
            }else {
                wordsTable.put(words[i],1);
            }
        }
        // 遍历哈希表，向优先级队列中添加元素
        Iterator<Map.Entry<String,Integer>> iterator =
                wordsTable.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String,Integer> entry =
                    iterator.next();
            queue.offer(entry.getKey());
            // 当队列中元素大于k个时，出队
            if (queue.size() > k)
                queue.poll();

        }
        // 当遍历完哈希表后，队列中存储了所有出现频次大于k的元素，按照降序排序，将顺序倒置输出即可。
        while (!queue.isEmpty()) {
            retList.add(queue.poll());
        }
        Collections.reverse(retList);
        return retList;
    }

    public static void main(String[] args) {
        String[] arr = new String[] {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> ret = new Num692().topKFrequent1(arr,1);
        System.out.println(ret);
    }

}
